import java.util.ArrayList;
import java.util.List;

public class PacificAtlantic {

    public static void main(String[] args) {
        PacificAtlantic pacificAtlantic = new PacificAtlantic();
        int[][] nums = {{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}};
        System.out.println(pacificAtlantic.pacificAtlantic(nums));
    }

    int[][] temp = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        List<List<Integer>> ans = new ArrayList<>();
        boolean[][] tag = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                tag = new boolean[m][n];
                int[] dfs = dfs(heights, i, j, m, n, Integer.MAX_VALUE, tag);
                if (dfs[0] == 1 && dfs[1] == 1) {
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
            }
        }
        return ans;
    }

    public int[] dfs(int[][] heights, int i, int j, int m, int n, int last, boolean[][] tag) {
        if (i < 0 || j < 0) {
            return new int[]{1, 0};
        }
        if (i >= m || j >= n) {
            return new int[]{0, 1};
        }
        if (heights[i][j] > last || tag[i][j]) return new int[]{0, 0};
        int flag = 2;
        tag[i][j] = true;
        for (int k = 0; k < temp.length; k++) {
            int[] dfs = dfs(heights, i + temp[k][0], j + temp[k][1], m, n, heights[i][j], tag);
            if (dfs[0] == 1) {
                if (flag == 1) return new int[]{1, 1};
                flag = 0;
            }
            if (dfs[1] == 1) {
                if (flag == 0) return new int[]{1, 1};
                flag = 1;
            }
        }
        tag[i][j] = false;
        if (flag == 2) return new int[]{0, 0};
        return flag == 1 ? new int[]{0, 1} : new int[]{1, 0};
    }
}
